package leetcode_100;

/**
 * 2018年5月16日 下午9:02:37
 * PartitionList_86 将一个链表按照传入的某个值分割成两个链表 最后组成一个链表 要求链表的比该值小的在一遍 另外的在另一边 不能破坏原始的顺序
 * @author 周杨
 * describe: 用两个结点监控 AC 100%
 *
 */
public class PartitionList_86 {
	static class ListNode {
		     int val;
		     ListNode next;
		     ListNode(int x) { val = x; }
		  }
	public static void main(String[] args) {
		PartitionList_86 test=new PartitionList_86();
		/*ListNode a=new ListNode(1);
		a.next=new ListNode(4);
		a.next.next=new ListNode(3);
		a.next.next.next=new ListNode(2);
		a.next.next.next.next=new ListNode(5);
		a.next.next.next.next.next=new ListNode(2);*/
		ListNode a=new ListNode(1);
		a.next=new ListNode(2);
		a.next.next=new ListNode(1);
		ListNode res=test.partition(a, 2);

	}
	
	public ListNode partition(ListNode head, int x) {
		if(head==null||head.next==null)
			return head;
		ListNode lHead=null,lTail=null,rHead=null,rTail=null,run=head;
		while(run!=null){
			if(run.val<x){
				if(lHead==null){
					lHead=run;
					lTail=run;
				}
				else{
					lTail.next=run;
					lTail=run;
				}
			}
			else{
				if(rHead==null){
					rHead=run;
					rTail=run;
				}
				else{
					rTail.next=run;
					rTail=run;
				}
			}
			run=run.next;
		}
		if(rTail!=null)
			rTail.next=null;
		if(lTail!=null)
			lTail.next=rHead;
	    return lHead==null?head:lHead;
	}
}
